package com.wtgroup.demo.leetcode.q042_接雨水;

/**
 * 双指针
 * <p>
 * 维护 leftMax, rightMax , 小的一端移动.
 *
 * 精妙.
 * @author 60906
 * @date 2021/5/4 17:41
 */
public class Q042_LC_双指针 {

    public int trap(int[] height) {
        int n = height.length;
        int left = 0, right = n-1;
        int leftMax = 0, rightMax = 0;
        int ans = 0;
        while (left < right) {
            // 边移动, 边更新 max 值
            leftMax = Math.max(height[left], leftMax);
            rightMax = Math.max(height[right], rightMax);
            // 小的一侧接水并移动, 小的, 对应 max 必更小
            if (height[left] < height[right]) {
                ans += leftMax - height[left];
                left++;
            } else {
                ans += rightMax - height[right];
                right--;
            }
        }

        return ans;
    }

}
